"""
斐波那契数列（Fibonacci sequence），又称黄金分割数列
因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入
故又称为“兔子数列”
1 2 3 4 5 6 7  8  9  10 11 12  13  14  15  16  17   18   19   20
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
"""


# 公式 F(n)=F(n-1)+F(n-2)
# 使用迭代的方式

def iteration(n):
    '返回斐波那契数列第n个值'
    n1 = 1  # 第一个数，这里为数列中的第一个数
    n2 = 1  # 第二个数，这里为数列中的第二个数
    # 当n等于 数列前两个数，返回1
    if n == 1 or n == 2:
        return 1
    # 第二个数之后，进行迭代
    while (n - 2) > 0:
        n3 = n2 + n1  # 为前两个数之和
        n1 = n2  # 将第二个数值赋给第一个数，向前进一位
        n2 = n3  # 将第三个数值赋给第二个数
        n -= 1  # 循环 n-2 次
    return n3


"""
print("使用迭代的方式")
number = int(input("请问您想获取第几位斐波那契数列的值:"))
result = iteration(number)
print("第 %d 位斐波那契数列的值为 %d" % (number, result))
"""


# 使用递归,超过一定值，效率特别慢
def recursion(n):
    if n == 1 or n == 2:
        return 1
    else:
        # F(n)=F(n-1)+F(n-2)
        return recursion(n - 1) + recursion(n - 2)


print("使用递归的方式")
number = int(input("请问您想获取第几位斐波那契数列的值:"))
result = recursion(number)
print("第 %d 位斐波那契数列的值为 %d" % (number, result))
